The present invention relates generally to image processing, and specifically to efficient compression of varying image data appearing in a fixed template, such as characters written on a form.
Businesses and organizations are increasingly turning to computerized storage of information filled in on documents such as paper forms, in addition to or in place of storing the forms themselves. After the form has been filled out, it is optically scanned and transferred to an electronic storage medium, such as a magnetic or optical disk. In order to ensure that the document is accurately reproduced when it is recalled from storage, it is necessary to scan the document at high resolution, typically on the order of 100 pixels/cm. To store an entire A4 page in this manner at eight bits/pixel, however, requires about 6 Mbytes of memory. Methods of image compression, as are known in the art, are applied to reduce the volume of data that must be recorded in order to reproduce a document.
A significant portion of the data in an image of a filled-in form corresponds to the form template, i.e., the lines, boxes, instructions, etc., that are preprinted on every form of a given type. Since this element of the form is predetermined and fixed, a useful way to reduce the volume of data that must be stored in recording the image of a filled-in form is to first remove the fixed template. Then the xe2x80x9cfill imagexe2x80x9dxe2x80x94what remains of the form after removal of the templatexe2x80x94is compressed and stored. Only a single image of the template needs to be stored, regardless of how many filled-in instances of a given form are to be stored and reproduced. To view the form as originally filled in, the template and fill images are recalled from memory and recombined. Another advantage of separating the fill image from the template is that it improves the accuracy of optical character recognition (OCR) programs used to interpret the characters in the fill image, which otherwise tends to be compromised by the presence of portions of the template near the characters.
U.S. Pat. Nos. 5,182,656, 5,204,756 and 5,793,887, which are incorporated herein by reference, describe methods for compressing and decompressing form images based on separation of the form template from the variable fill portion of the form. These patents are concerned mainly with improving the accuracy of registration of a pre-stored template image with the scanned document image that is to be compressed, so that the template can be more precisely removed from the image before compression and restored upon decompression. As is common in the art of document imaging, the methods of these patents address only binary images and do not relate to the distribution of gray levels in the actual document or in images captured thereof. Furthermore, these patents do not address problems that can arise when portions of the characters in the fill portion of the form overlap elements of the template. As a result of such overlap, when the template is removed from the document image, gaps may be left in some of the characters. Thus, improved image compression may be achieved, but at the expense of reduced readability in the stored images.
It is an object of the present invention to provide improved methods for compressing and decompressing images of filled-in form documents.
It is a further object of some aspects of the present invention to provide methods for improving readability of form document images following decompression.
In preferred embodiments of the present invention, a document scanner captures a gray-level image of a filled-in form document, based on a form template. An image of the template is removed from the captured image, as is known in the art. Groups of pixels in the image that remains having gray-level values below a given threshold are identified as belonging to a bi-level kernel of the image. The kernel thus defines the shapes of the characters that were filled into the form. A gray-level value is recorded for each of the pixels in the kernel, corresponding to the original value of the pixel in the captured image. A halo is defined surrounding the kernel, preferably by morphologically expanding the kernel by a predetermined amount in all directions, typically by a single pixel. For each of the pixels in the halo, the gray-level value from the captured image is recorded. Preferably, adjoining gray-level values are grouped together, and the gray-level resolution is reduced, most preferably to a user-selectable degree, so as to reduce the volume of gray-level data that must be stored. The gray-level data for both the kernel and halo pixels are then compressed, using any suitable algorithm known in the art. Both the kernel and the compressed gray-level data are stored in a memory.
Preferably, gray-level information in the image is used to close any gaps that may be left in characters in the kernel due to removal of the template, most preferably using methods described in European Patent Application 98480087.0, which is assigned to the assignee of the present patent application and incorporated herein by reference. Alternatively, the gaps are closed using methods based on distance transforms, as described in a U.S. Patent Application, filed on even date, entitled xe2x80x9cSeparating Text from Form Data in Document Images,xe2x80x9d which is assigned to the assignee of the present patent application and incorporated herein by reference. It will be understood, however, that while such gap-closing is desirable, and may be carried out using any suitable method known in the art, it is not essential to the present invention.
In order to reconstruct the image, an image of the template and the bi-level kernel are recalled from memory and combined in proper registration. The stored gray-level data are then decompressed and assigned to the appropriate pixels in the kernel and the halo. Preferably, the image of the template includes gray-level data, as well. At points of overlap between the kernel and features of the template, such as lines and text, substitute gray-level values are preferably computed so as to blend with the adjacent points of the kernel and of the template features. Similarly, at points at which the halo overlaps a dark or gray portion of the template, the gray-level values assigned to the halo may be replaced by darker values in the template.
In this manner, an image is reconstructed of the filled-in form that is more faithful to the actual appearance of the original, and is therefore easier and more pleasing to read than binary images of the form as are known in the art. While the volume of data storage required for a typical compressed gray-level image, in accordance with preferred embodiments of the present invention, is greater than for the binary image alone, it is still far less than could be achieved by conventional methods of gray-scale image compression.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for compressing an electronic image of an object including gray-level information, including:
processing the gray-level information to identify a kernel of pixels in the image having respective gray-level values darker than a given kernel threshold;
storing a locus of the pixels in the kernel in a memory; and
storing in the memory the gray-level values of the pixels in the kernel, in order to reconstruct a gray-level image of the object by applying the stored gray-level values to the pixels in the locus.
Preferably, the object includes a document, and processing the gray-level information includes identifying a kernel corresponding to information in the document. Most preferably, the document includes a form having a template printed thereon, and processing the gray-level information includes separating an image of the template from characters filled into the template using gray-level values of pixels corresponding to the template and to the characters. In a preferred embodiment, separating the image of the template from the characters includes removing the image of the template from an image of the characters and filling gaps left in the characters due to removal of the template image using the gray-level information.
Preferably, the method includes reconstructing the image by combining stored gray-level values corresponding to the image of the template with the stored locus and gray-level values of the pixels in the kernel, wherein combining the stored gray-level values corresponding to the image of the template with the gray-level values of the pixels in the kernel includes computing a combined gray-level value for a pixel at which the locus of the kernel overlaps with the image of the template. In a preferred embodiment, computing the combined gray-level value includes computing a normalized product of gray-level values from the kernel and from the template.
In a preferred embodiment, the method includes defining a halo in the image surrounding the kernel and storing in the memory the gray-level values of the pixels in the halo, for use in reconstructing the image. Preferably, defining the halo includes morphologically expanding the locus of the kernel. Most preferably, the method includes reconstructing the image by morphologically expanding the locus of the kernel and applying the stored gray-level values of the pixels in the halo to the expanded locus, wherein a locus of the pixels in the halo is not stored along with the stored locus of the kernel.
Preferably, storing the gray-level values of the pixels in the halo includes grouping the pixels by the respective gray-level values so as to reduce a volume of data to be stored. In a preferred embodiment, grouping the pixels includes masking one or more bits of the gray-levels values of the pixels, wherein masking the one or more bits includes eliminating from the halo pixels having gray-level values beyond a given halo threshold. Most preferably, the method includes storing a locus of the bits remaining in the halo after the pixels having gray-level values beyond the given halo threshold are eliminated therefrom.
Alternatively, grouping the pixels includes selecting a number of groups into which the pixels are to be divided and storing for each of the groups a respective representative gray-level value to for all of the pixels in the group.
In a preferred embodiment, the image to be compressed has a background including predetermined gray-level values of pixels therein, which are not stored along with the gray-level values of the pixels in the kernel and the halo, and the method includes reconstructing the image by combining the stored gray-level values of the pixels in the kernel and the halo with the gray-level values of the pixels in the background. Preferably, combining the stored gray-level values of the pixels in the halo with the gray-level values of the pixels in the background includes selecting for the reconstruction at each pixel of the halo the darker of the respective stored gray levels of the pixel.
Preferably, storing the gray-level values of the pixels in the kernel and in the halo includes storing the values as one or more continuous blocks of data and compressing the data in the blocks.
There is further provided, in accordance with a preferred embodiment of the present invention, a method for compressing an electronic image of an object including gray-level information, including:
processing the gray-level information to identify a first group of pixels in the image having respective gray-level values darker than a first threshold;
processing the gray-level information to identify a second group of pixels in the image, in proximity to pixels in the first group, having respective gray-level values lighter than the first threshold; and
storing the gray-level values of the pixels in the first and second groups in a memory, in order to reconstruct a gray-level image of the object by applying the stored gray-level values to the respective pixels in the first and second groups.
Preferably, processing the gray-level information to identify the first group of pixels includes finding a locus of the pixels in the first group, and processing the gray-level information to identify the second group of pixels includes selecting pixels in a halo surrounding the locus of the first group, wherein selecting the pixels in the halo includes morphologically expanding the locus.
In a preferred embodiment, processing the gray-level information to identify the second group of pixels in the image includes selecting only pixels having gray-level values darker than a second threshold for inclusion in the second group.
Preferably, the object includes a document, and wherein processing the gray-level information includes identifying pixels corresponding to information content of the document. Most preferably, the document includes a preprinted template, and wherein processing the gray-level information to identify the first group includes eliminating the template from the image to be processed.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for reconstructing an electronic image of a document having a template preprinted thereon, the image including information filled into the template, including:
receiving stored gray-level data corresponding to an image of the template;
receiving stored gray-level data corresponding to the information filled into the template; and
combining the data corresponding to the images of the template and of the information in mutual registration to produce an output gray-level image of the document.
Preferably, the template represents a form, and wherein the information filled into the template includes characters written on the form.
Further preferably, the stored gray-level data corresponding to the image of the information includes a kernel, identifying a locus of pixels containing the information, and wherein combining the data includes applying respective stored gray-level values to the pixels in the kernel. Most preferably, combining the data includes finding a pixel at which the kernel intersects with a feature of the template and computing an output gray-level value of the pixel by combining respective stored gray-level values of the pixel in the image of the template and of the information.
In a preferred embodiment, the stored gray-level data corresponding to the information includes a halo of pixels surrounding the kernel and having gray-level values lighter than the values of the pixels in the kernel. Preferably, the stored gray-level data corresponding to the image of the template includes a background, and combining the images includes computing an output gray-level value of a pixel in the halo by combining respective stored gray-levels of the pixel in the background and in the information.
There is additionally provided, in accordance with a preferred embodiment of the present invention, apparatus for compressing an electronic image of an object including gray-level information, including:
a processor, which processes the gray-level information to identify a kernel of pixels in the image having respective gray-level values darker than a given kernel threshold; and
a memory, in which the processor stores a locus of the pixels in the kernel along with the gray-level values of the pixels, whereby a gray-level image of the object is reconstructed by applying the stored gray-level values to the pixels in the locus.
In a preferred embodiment, the apparatus includes an image output device, wherein the processor reconstructs the image by combining stored gray-level values corresponding to the image of the template with the stored locus and gray-level values of the pixels in the kernel and outputs the reconstructed image to the output device.
There is moreover provided, in accordance with ape of the present invention, apparatus for compressing an electronic image of an object including gray-level information, including:
a processor, which processes the gray-level information to identify a first group of pixels in the image having respective gray-level values darker than a first threshold and a second group of pixels in the image, in proximity to pixels in the first group, having respective gray-level values lighter than the first threshold; and
a memory, in which the processor stores the gray-level values of the pixels in the first and second groups, whereby a gray-level image of the object is reconstructed by applying the gray-level values to the respective pixels in the first and second groups.
There is additionally provided, in accordance with a preferred embodiment of the present invention, apparatus for reconstructing an electronic image of a document having a template preprinted thereon, the image including information filled into the template, including:
a processor, which receives stored gray-level data corresponding to an image of the template and to the information filled into the template, and which combines the data corresponding to the image of the template and the information in mutual registration to produce an output gray-level image of the document; and
an image output device, which receives and displays the output gray-level image.
There is further provided, in accordance with a preferred embodiment of the present invention, a computer software product including computer-readable instructions in an executable file, which when run by a computer that receives an electronic gray-level image of an object, causes the computer to process the image so as to identify a kernel of pixels in the image having respective gray-level values darker than a given kernel threshold, and to store in a memory a locus of the pixels in the kernel along with gray-level values of the pixels in the kernel, to be used in reconstructing the gray-level image of the object by applying the stored gray-level values to the pixels in the locus.
Preferably, the object includes a form document having a template printed thereon, and wherein the instructions cause the computer to separate an image of the template from characters filled into the template using gray-level values of pixels corresponding to the template and to the characters.
There is also provided, in accordance with a preferred embodiment of the present invention, a computer software product including computer-readable instructions in an executable file, which when run by a computer that receives an electronic gray-level image of an object, causes the computer to process the gray-level information to identify a first group of pixels in the image having respective gray-level values darker than a first threshold and a second group of pixels in the image, in proximity to pixels in the first group, having respective gray-level values lighter than the first threshold, and to store the gray-level values of the pixels in the first and second groups in the memory, to be used in reconstructing a gray-level image of the object by applying the gray-level values to the respective pixels in the first and second groups.
There is furthermore provided, in accordance with preferred embodiment of the present invention, a computer software product including computer-readable instructions in an executable file, which when run by a computer, causes the computer to recall from a memory stored gray-level data corresponding to an image of a template preprinted on a form document and further to recall stored gray-level image data corresponding to information that was filled into the template, and to combine the data corresponding to the image of the template and to the information in mutual registration to produce an output gray-level image of the document.